package org.example.SolutionNew001;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class SubString03 {
    public static void main(String[] args) {
        SubString03 obj = new SubString03();
        String s="acbbaca";
        String t="aba";
        System.out.println(obj.minWindow(s, t));

    }

    public String minWindow0(String s, String t) {
        int start=0,length=Integer.MAX_VALUE,n=s.length();
        Set<Character> set=new HashSet<>();
        int asciiSize=97+26-1-65+1;
        int[] tarr=new int[asciiSize];
        int[] sarr=new int[asciiSize];
        for(char c:t.toCharArray()){
            set.add(c);
            tarr[c-'A']++;
        }
        while(start<n&&!set.contains(s.charAt(start))) start++;
        int tmpLength=0;
        for(int i=start,j=start;i<n;i++){
            char c=s.charAt(i);
            tmpLength++;
            if(set.contains(c)&&sarr[c-'A']<tarr[c-'A']) {
                sarr[c-'A']++;
                if(Arrays.equals(tarr,sarr)&&tmpLength<length){
                    length=tmpLength;
                    start=j;
                    sarr[s.charAt(start)-'A']--;
                    do {
                        j++;tmpLength--;
                    }while(j<=i&&!set.contains(s.charAt(j)));
                }else if(Arrays.equals(tarr,sarr)&&tmpLength>=length){
                    sarr[s.charAt(j)-'A']--;
                    do {
                        j++;tmpLength--;
                    }while(j<=i&&!set.contains(s.charAt(j)));
                }
            }else if(set.contains(c)&&sarr[c-'A']>=tarr[c-'A']&&c==s.charAt(j)){
                j++;tmpLength--;
                while(!set.contains(s.charAt(j))){
                    j++;tmpLength--;
                }
            }
        }
        if(length<=n){
            return s.substring(start,start+length);
        }else return "";
    }

    public String minWindow(String s, String t) {
        int n=s.length(),m=t.length();
        if(m>n) return "";
        int[] map=new int[58];
        for(char c:t.toCharArray()){
            map[c-'A']++;
        }

        int left=0,right=0;
        int minLeft=0,minLen=Integer.MAX_VALUE;
        int count=t.length();

        while(right<n){
            char c=s.charAt(right);
            if(map[c-'A']>0) count--;
            map[c-'A']--;

            while(count==0){
                if(right-left+1<minLen){
                    minLen=right-left+1;
                    minLeft=left;
                }
                char c1=s.charAt(left);
                if(++map[c1-'A']>0) count++;
                left++;
            }
            right++;

        }
        return minLen==Integer.MIN_VALUE?"":s.substring(minLeft,minLeft+minLen);
    }
}
